package sorting

import "gitee.com/guuzaa/sorting/constraints"

func PatienceSort[T constraints.Ordered](arr []T) []T {
	var piles [][]T

	for _, poker := range arr {
		left, right := 0, len(piles)
		for left < right {
			mid := left + (right-left)/2
			if piles[mid][len(piles[mid])-1] >= poker {
				right = mid
			} else {
				left = mid + 1
			}
		}

		if left == len(piles) {
			piles = append(piles, []T{poker})
		} else {
			piles[left] = append(piles[left], poker)
		}
	}

	return mergePiles(piles)
}

func mergePiles[T constraints.Ordered](piles [][]T) []T {
	var ret []T

	for len(piles) > 0 {
		id := 0
		minV := piles[id][len(piles[id])-1]

		for i := 1; i < len(piles); i++ {
			if minV > piles[i][len(piles[i])-1] {
				minV = piles[i][len(piles[i])-1]
				id = i
			}
		}

		ret = append(ret, minV)
		piles[id] = piles[id][:len(piles[id])-1]
		if len(piles[id]) == 0 {
			piles = append(piles[:id], piles[id+1:]...)
		}
	}

	return ret
}
